package leetcode.D900.T875;

class Solution {
    /* 暴力法（超时）
    public int minEatingSpeed(int[] piles, int h) {
        int i, maxPile = Integer.MIN_VALUE;
        for(i=0; i<piles.length; ++i) {
            maxPile = Math.max(maxPile, piles[i]);
        }
        for(i=1; i<=maxPile; ++i) {
            int sum = getTime(piles, i);
            if(sum > 0 && sum <= h) {
                break;
            }
        }
        return i;
    }*/

    // 二分法搜索
//    public int minEatingSpeed(int[] piles, int h) {
//        int maxPile = Integer.MIN_VALUE;
//        for(int i=0; i<piles.length; ++i) {
//            maxPile = Math.max(maxPile, piles[i]);
//        }
//        int left = 1, right = maxPile;
//        while(left < right) {
//            int mid = left + (right - left) / 2;
//            int sum = getTime(piles, mid);
//            if(sum <= h) {
//                right = mid;
//            } else {
//                left = mid + 1;
//            }
//        }
//        return left;
//    }
//    private int getTime(int[] piles, int k) {
//        int sum = 0;
//        for(int i=0; i<piles.length; ++i) {
//            int a = piles[i] / k;
//            sum += (piles[i] % k == 0 ? a : a+1);
//            if(sum < 0) return Integer.MAX_VALUE;
//        }
//        return sum;
//    }

    // 二刷
    /*public int minEatingSpeed(int[] piles, int h) {
        int maxPile = 0;
        for (int x : piles) {
            maxPile = Integer.max(maxPile, x);
        }
        int left = 1, right = maxPile;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(getTime(piles, mid) > h) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private int getTime(int[] piles, int k) {
        int sumTime = 0;
        for(int i=0; i<piles.length; ++i) {
            sumTime += ((int) piles[i] / k);
            if(piles[i] % k > 0) {
                sumTime++;
            }
            if(sumTime < 0) {
                return Integer.MAX_VALUE;
            }
        }
        return sumTime;
    }*/

    // 三刷
    public int minEatingSpeed(int[] piles, int h) {
        int right = 0, left = 1;
        for (int i = 0; i < piles.length; i++) {
            right = Math.max(piles[i], right);
        }
        while(left < right) {
            int mid = left + (right - left) / 2;
            if (canSuccess(piles, mid, h)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean canSuccess(int[] piles, int speed, int totolTime) {
        int needTime = 0;
        for (int i = 0; i < piles.length; i++) {
            needTime += (piles[i]%speed==0) ? piles[i]/speed : piles[i]/speed+1;
        }
        return needTime <= totolTime;
    }
}